#include <iostream>
#include <string>
#include <assert.h>
#include <time.h>
#include "structures.h"
#include <QProgressBar>
#include <QApplication>
#include "McCreight.h"
#include "ConstrArbre2.h"


dico2* MacCreight(char *chaine, QProgressBar* bar,float *temps)
{
	/* L'algorithme prend en parametre une chaine de caractere
	et retourne le pointeur vers l'arbre correspondant a la chaine de caractere
	L'algorithme est celui realise par Mc Creight en 1976 */
	
	dico2 *Racine,*Noeud, *U;unsigned int av = 0,pourcent=0;;
	creernoeud2(&Racine);//On initialise l'arbre vec la racine
	/*ici on utilise une varible pour avancer dans la chaine*/
	clock_t	temps_initial, temps_final;
	float temps_cpu=0; 
	Noeud=Racine;
	unsigned int avanc = 0, avanc2 = 0 , taille = 0 ,j;
	temps_initial = clock ();
	unsigned int az=strlen(chaine);
	
	
	for( unsigned int i = 0 ; i < az ; i++)
	{
		
		if((i*100)/strlen(chaine)!=pourcent)
		{
			
			
			pourcent=(i*100)/strlen(chaine);
			bar->setValue(pourcent);
			bar->repaint();
			bar->update();
			bar->update();
			bar->update();
			QApplication::processEvents();
			
		}
	
		if( Racine == Noeud)//si le noeud égale la racine alors on fait la recherche à partir de la racine
		{
	
			
			avanc=Recherche(&Noeud,chaine,i);//fonction commune avec la recherche naive dans fichier ConstrArbre.c
			
			j=convert_car(chaine[avanc]);//fonction dans fichier ContrArbre.c
		
			creernoeud2(&(*Noeud).fils[j]);//fonction dans fichier ContrArbre.c
		
			(*(*Noeud).fils[j]).DebutRacine=i+1;
			(*(*Noeud).fils[j]).debut=avanc+1;
			(*(*Noeud).fils[j]).taille=strlen(chaine)-avanc;
			(*(*Noeud).fils[j]).pere=(Noeud);
			(*(*Noeud).fils[j]).fils[5]=NULL;
			
		}
		else//sinon
		{
			if(Noeud->fils[5]!=NULL)//si le suffixe n'est pas nulle
			{
				
				assert((*Noeud).fils[5]!=NULL);
				U=(*Noeud).fils[5];//on récupère le suffixe
				
				avanc=(*U).debut-1;
				av=avanc2;
			}
			else//sinon
			{
				
				
				avanc2=(*Noeud).debut-1;//on récupère la branche pere(p) p
				taille =(*Noeud).taille;
				
				assert((*Noeud).pere!=NULL);
				
				if((*Noeud).pere==Racine)/*si pere(p) est la racine alors on retire un caractère et on fait la recherche à partir de la racine*/
				{
					
					avanc2++;taille--;av=avanc2;
					
					U=Rech_Rapide(Racine,chaine,&avanc2,taille);
				
					
				}
				else//sinon on fait une recherche rapide
				{
					
					av=avanc2;
					if((*(*Noeud).pere).fils[5]==NULL)
					{
					
					
						
						return 0 ;
					}
					
					
						
						assert((*(*Noeud).pere).fils[5]!=NULL);
						U=Rech_Rapide((*(*Noeud).pere).fils[5],chaine,&avanc2,taille);
					
					
					
					
				}
				

				(*Noeud).fils[5]=U;
				
	
				/*On cree le lien suffixe*/
			}
			Noeud=U;//On déplace le noeud
	
			
			
			
			
			
			avanc=Recherche(&Noeud,chaine,i+((*Noeud).debut-(*Noeud).DebutRacine)+(*Noeud).taille);//on fait une recherche à partir du nouveau noeud.... 
			j=convert_car(chaine[avanc]);
		
			
			creernoeud2(&(*Noeud).fils[j]);
			(*(*Noeud).fils[j]).DebutRacine=i+1;//on cree la branche voulu
			(*(*Noeud).fils[j]).debut=avanc+1;
			(*(*Noeud).fils[j]).taille=strlen(chaine)-avanc;
			(*(*Noeud).fils[j]).pere=(Noeud);
			
		
			
			
		
		}
		
	}
	
	temps_final = clock ();

	temps_cpu = (temps_final - temps_initial) ;
	
	
	assert(Racine!=NULL);
	*temps = (temps_cpu)/CLOCKS_PER_SEC;
	return Racine;
}

dico2* Rech_Rapide(dico2* Racine,char* chaine,unsigned int *av,unsigned int taille)//erreur dans recherche rapide...A refaire
{
/* prend en parametre une chaine et un noeud de l'arbre, renvoie le noeud à partir duquel la chaine et celles présentent dans l'arbre diffère*/



	unsigned int j,aVinf=0,av2=*av;//aVinf correspond a avancement inférieur, c'est l'endroit de la chaine qui correspond a la branche ou on est situe (branche deja presente)
	//alors que av correspond a l'endroit de la chaine qui servira a construire la futur branche
	while(*av<strlen(chaine) && *av-av2< taille)
	{

		j=convert_car(chaine[*av]);

		if((*Racine).fils[j]!=NULL)//si il existe une branche qui correspond a cette suite de caractère on y va
		{

			aVinf=(*(*Racine).fils[j]).debut-1;

			while(aVinf-(*(*Racine).fils[j]).debut+1<(*(*Racine).fils[j]).taille  && chaine[aVinf]==chaine[*av] && *av-av2<taille)
			{
			
				aVinf++;*av=*av+1;// on avance dans la branche
			}
			if ((*(*Racine).fils[j]).taille<=aVinf-(*(*Racine).fils[j]).debut+1)//Si on a atteint la fin de la branche on change de noeud
			{
				Racine=(*Racine).fils[j];
			}
			else//sinon c'est que la branche décrivant notre suite de caractere n'existe pas, donc on cree un noeud a cette endroit
			{	
				CoupeArc2(&(*Racine).fils[j],aVinf,chaine);// A ARRANGER !
				(*(*Racine).fils[j]).pere=(Racine);
				Racine=(*Racine).fils[j];//on se positionne sur le noeud
				return Racine;//on renvoit le debut de la suite de caractere qui correspondra a la futur branche
			}
		}
		else
		{
		return Racine;//si il n'existe pas de branche presentant la suite de caractere, on renvoit le debut de la chaine qui correspondra a la futur branche
		}
		
	}


	return Racine;
}
